#include<unordered_map>
#include<list>
#include<string>
#include<set>
class AllOne {
public:
    std::unordered_map<std::string, std::list<std::pair<int,std::set<std::string>>>::iterator> myMap;
    std::list<std::pair<int,std::set<std::string>>> myList;
    AllOne() {
        
    }
    
    void inc(std::string key) {
        if (myMap.find(key) == myMap.end())
        {
            //notfind
            if (myList.empty())
            {
                //empty
                myList.push_back({1,{key}});
                auto list_iterator = myList.begin();
                myMap.insert({key,list_iterator});
            }else
            {
                //notempty
                auto list_iterator = myList.begin();
                if (list_iterator->first==1)
                {
                    list_iterator->second.insert(key);
                    myMap.insert({key,list_iterator});
                }else
                {
                    myList.push_front({1,{key}});
                    myMap.insert({key,myList.begin()});
                }
            }
        }
        else
        {
            //find
            auto list_iterator = myMap[key];
            int nextvalue = list_iterator->first+1;
            auto list_next= std::next(list_iterator);
            if (list_next==myList.end())
            {
                myList.push_back({nextvalue,{key}});
                myMap[key] =std::prev( myList.end());
                list_iterator->second.erase(key);
                if (list_iterator->second.empty()) myList.erase(list_iterator);
            }
          else if (list_next->first==nextvalue)
          {
              list_iterator->second.erase(key);
              if (list_iterator->second.empty()) myList.erase(list_iterator);
              list_next->second.insert(key);
              myMap[key]=list_next;
          }
            else
          {
             myList.insert(list_next,{nextvalue,{key}});
              myMap[key]=std::next(list_iterator);
              
              list_iterator->second.erase(key);
              if (list_iterator->second.empty()) myList.erase(list_iterator);
              
          }
        }
    }
    
    void dec(std::string key) {
        if (myMap.find(key) == myMap.end()) return;
        auto list_iterator = myMap[key];
        int preValue = list_iterator->first-1;
       
if (preValue==0)
{
    list_iterator->second.erase(key);
    if (list_iterator->second.empty()) myList.erase(list_iterator);
    myMap.erase(key);
    return;
}
        
        if (list_iterator == myList.begin())
        {
            
            myList.push_front({1,{key}});
            myMap[key] = myList.begin();
            list_iterator->second.erase(key);
            if (list_iterator->second.empty()) myList.erase(list_iterator);
            return;
        }
        
        auto list_prev = std::prev(list_iterator);

        if (list_prev->first == preValue)
        {
            myMap[key]=list_prev;
            list_prev->second.insert(key);
            list_iterator->second.erase(key);
            if (list_iterator->second.empty()) myList.erase(list_iterator);
        }else
        {
            myList.insert(list_iterator,{preValue,{key}});
            myMap[key]=std::prev(list_iterator);
            list_iterator->second.erase(key);
            if (list_iterator->second.empty()) myList.erase(list_iterator);
        }
        
    }
    
    std::string getMaxKey() {
       if (myMap.empty()) return "";
        auto list_iterator =std::prev( myList.end());
        return *(list_iterator->second.begin());
    }
    
   std:: string getMinKey() {
        if (myMap.empty()) return "";
        auto list_iterator = myList.begin();
        return *(list_iterator->second.begin());
    }
};
